package example3;

import java.util.HashSet;
import java.util.Set;

//208. 实现 Trie (前缀树)
public class LeetCode208 {
    public static void main(String[] args) {

    }
}

class Trie {
    public Trie[] children;

    public boolean isEnd;

    public Trie() {
        this.children = new Trie[26];
        this.isEnd = false;
    }

    public void insert(String word) {
        Trie node = this;
        for(int i=0;i<word.length();i++){
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null){
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    public Trie searchPrefix(String prefix){
        if(prefix == null || prefix.equals("")) return null;
        Trie node = this;
        for(int i=0;i<prefix.length();i++){
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null)    return null;
            node = node.children[index];
        }
        return node;
    }
}

class Trie1 {
    private Set<String> set = new HashSet<>();

    private Set<String> prefixes = new HashSet<>();

    public Trie1() {

    }

    public void insert(String word) {
        set.add(word);
        prefixes.add(word);
        for(int i=1;i<word.length();i++){
            prefixes.add(word.substring(0,i));
        }
    }

    public boolean search(String word) {
        return set.contains(word);
    }

    public boolean startsWith(String prefix) {
//        for(String s : set){
//            if(s.startsWith(prefix))    return true;
//        }
//        return false;
        return prefixes.contains(prefix);
    }
}
